Uma \emph{CDN} é uma rede de servidores que cooperam entre si para fornecer conteúdos aos clientes de tal rede. Se os clientes se conectam com os servidores através de uma rede móvel, podemos chamar a CDN de \emph{Mobile Content Distribution Network (MCDN)}.

\begin{figure}[h]
    \centering
    \includegraphics[scale=0.15]{../presentations/implementation/images/wired_cdn.png}
    \includegraphics[scale=0.15]{../presentations/implementation/images/mobility.png}

    \caption{Uma \emph{CDN} comum e uma \emph{MCDN}}
\end{figure}

Em uma \emph{CDN}, um servidor é chamado de \emph{servidor origem} de um conteúdo se é responsável por esse conteúdo. Um conteúdo deve sempre estar disponível em seu \emph{servidor origem}.

Quando um cliente se conecta a um servidor e faz um requisição por um conteúdo, o servidor pode responder a essa requisição por \emph{serviço direto} ou por \emph{serviço indireto}.

\begin{itemize}
    \item \emph{Serviço direto} O servidor $S$ possui o conteúdo $C$ requisitado pelo cliente. O servidor $S$ simplesmente responde a requisição com o conteúdo $C$. \emph{Serviço direto} não gera tráfego no \emph{backbone} da \emph{CDN}.

    \begin{figure}[h]
        \centering
        \includegraphics[scale=0.3]{../presentations/implementation/images/direct_service.png}

        \caption{Exemplo de \emph{serviço direto}}
    \end{figure}

    \item \emph{Serviço indireto} O servidor $S$ não possui o conteúdo $C$ requisitado pelo cliente. O servidor $S$ encaminha a requisição para o servidor $S_{i}$ que possui o conteúdo $C$. O servidor $S_{i}$ envia uma cópia do conteúdo $C$ para o servidor $S$, por fim, essa cópia é enviada ao cliente. \emph{Serviço indireto} gera tráfego no \emph{backbone} da \emph{CDN}.

    \begin{figure}[h]
        \centering
        \includegraphics[scale=0.3]{./images/indirect_service.png}

        \caption{Exemplo de \emph{serviço indireto}}
    \end{figure}

\end{itemize}

Observação: Um servidor $S$ possui um conteúdo $C$ se é o \emph{servidor origem} de $C$ ou se possui uma réplica de $C$.

No artigo \cite{aioffi05}, os dois principais objetivos propostos são: reduzir o tráfego no \emph{backbone} da rede e impedir a sobrecarga dos servidores. Ambos objetivos são atacados através de replicação de conteúdos.

Uma \emph{réplica} de um conteúdo $C$ é uma cópia desse conteúdo armazenada por um servidor para algum propósito, como por exemplo, reduzir o tempo de resposta dos clientes que fazem requisições por $C$.

\emph{Replicação} acontece da seguinte forma. O servidor $S$ decide replicar o conteúdo $C$ e envia um pedido de replicação para o servidor $S_{r}$. O servidor $S_{r}$ envia uma cópia de $C$ pelo \emph{backbone} da \emph{CDN} para $S$. O servidor $S$, ao receber a cópia, a armazena.

\begin{figure}[h]
    \centering
    \includegraphics[scale=0.3]{./images/replication.png}

    \caption{Exemplo de \emph{replicação} de um conteúdo}
\end{figure}

Réplicas sofrem o problema de \emph{falta de atualização}. Uma réplica $C_{r}$ armazenada por um longo período de tempo no servidor $S$ pode estar desatualizada em relação ao conteúdo original $C_{o}$. Nesses casos, o Servidor $S$ deve receber uma nova cópia de $C_{o}$ ou \emph{patches} com as alterações de $C_{o}$, a isso é dado o nome de manutenção. A \emph{manutençao de uma réplica} gera tráfego no \emph{backbone} da \emph{CDN}.

Portanto, o tráfego no \emph{backbone} de uma \emph{CDN} é gerado, basicamente, por três tipos de operação: \emph{serviços indiretos}, \emph{replicação de conteúdos} e \emph{manutenção de réplicas}. Os dois algoritmos propostos utilizam medidas dessas operações para decidir como gerenciar conteúdos.

\subsection{\emph{Algoritmo Heurístico Online}}

O \emph{algoritmo heurístico online} descrito em \cite{aioffi05} busca prever os custos de \emph{manutenção}, \emph{serviços indiretos} e \emph{replicaçao} de um conteúdo $C$. Pela comparação desses custos, o servidor decide uma ação a ser tomada. As possíveis ações são \emph{remoção de conteúdo}, \emph{pull de uma réplica} e \emph{push de uma réplica}.

\begin{algorithm}[H]

    \small
    \SetLine

    \For{$\forall$ conteúdo $c \in C$}{
        \For{$k \leftarrow 1, \cdots, \delta$}{$\hat{y}_{t + k} \leftarrow DES(c, i, t, k)$}
        $d^{ic} \leftarrow \sum \limits ^{\delta}_{k = 1} \hat{y}_{t + k}$\\
        $bi^{c} \leftarrow d^{ic} \times si^{c} \times dist_{i, j}$\\
        $br^{c} \leftarrow sr^{c} \times dist_{i, j}$\\
        $bm^{c} \leftarrow \sum \limits ^{\delta}_{k = 1} m^{t + k, c} \times sm^{c} \times dist_{i, o^{c}}$\\
        \uIf{não possuo o conteúdo $c$}{
            \If{$bi^{c} > (br^{c} + bm^{c})$}{Replico o conteúdo $c$ da réplica mais próxima}
        }
        \ElseIf{possuo o conteúdo $c$ e não sou o servidor origem de $c$}{
            \If{$bi^{c} > bm^{c}$}{Removo o conteudo $c$}
        }
    }

    \caption{Algoritmo Heurístico Online, políticas de \emph{pull} e remoção}
    \label{ahopull}
\end{algorithm}

\begin{algorithm}[h]

    \small
    \SetLine

    $load_{i} \leftarrow 0$\\
    \For{$\forall j \in {S - i}$}{
        \For{$\forall c \in C \mid a^{tc}_{i} = 1$}
        {
            \For{$k \leftarrow 1$ \KwTo $\delta$}
            {
                $\hat{y}^{jc}_{indirect_{t + k}} \leftarrow DES(c, i, t, k)$\\
                $load_{i} \leftarrow  load_{i} + \hat{y}^{jc}_{indirect_{t + k}}$\\
            }
            $d^{ic}_{j} \leftarrow \sum \limits ^{\delta}_{k = 1} \hat{y}^{jc}_{indirect_{t + k}}$\\
        }
    }
    \While{$load_{i} > HW$}{
        Fazer \emph{push} da réplica do conteúdo $c$ para $j \in S$ tal que $\max(d^{ic}_{j})$\\
        $load_{i} \leftarrow load_{i} - d^{ic}_{j}$\\
    }

    \caption{Algoritmo Heurístico Online, política de \emph{push}}
    \label{ahopush}
\end{algorithm}

Os algoritmos \ref{ahopull} e \ref{ahopush} são executados em cada servidor durante o período de reconfiguração.

\subsection{Implantação}

Para a implantação do \emph{algoritmo heurístico online}, foram criadas as seguintes estruturas de dados principais:

\begin{itemize}

    \item \emph{Vetor de lista de servidores (VLS)}. Esse vetor possui uma célula para cada conteúdo, o índice da célula representa o conteúdo. A lista de servidores de uma célula representa quais servidores possuem o conteúdo. Cada servidor na \emph{MCDN} possui um vetor desses.

    \begin{figure}[h]
        \centering
        \includegraphics[scale=0.6]{images/servers_for_content.png}

        \caption{Lista de servidores que possuem um conteúdo}
        \label{servers_for_content}
    \end{figure}

    \item \emph{Lista de operações (LO)}. É uma lista em que cada operação é um registro contendo: o tipo de de operação, \emph{pull}, \emph{push} ou \emph{remoção}; o conteúdo sobre o qual a operação será realizada e o servidor que a operação afetará. Cada servidor na \emph{MCDN} possui uma lista dessas.

    \begin{figure}[h]
        \centering
        \includegraphics[scale=0.6]{images/operation_list.png}

        \caption{Lista de operação efetuadas por um servidor}
    \end{figure}

\end{itemize}

O problema do algoritmo distribuído para \emph{MCDN} reside em manter o \emph{VLS} consistente entre todos os servidores. Isso é o mesmo que dizer que todos os servidores devem saber em quais servidores um dado conteúdo existe.

Para manter a consistência do vetor de lista de servidores usa-se a lista de operações. Quando a simulação se inicia, não há réplicas, apenas conteúdos em seus \emph{servidores origens}. Essa informação é armazenada por padrão em todos.

Ao longo da simulação, réplicas são criadas ou removidas de servidores, isso afeta a consistência do \emph{VLS}. A solução para estabelecer a consistência do \emph{(VLS)} é cada servidor comunicar as operações que efetuará aos demais servidores. Para isso, cada servidor deve popular a sua própria lista de operações de acordo com as decisões tomadas no \emph{algoritmo heurístico online}.

\begin{algorithm}[H]

    \small
    \SetLine

    \For{$\forall$ conteúdo $c \in C$}{
      $\vdots$\\
      \uIf{não possuo o conteúdo $c$ e $bi^{c} > (br^{c} + bm^{c})$}{
        \emph{\textbf{Insiro na minha lista de operações o \emph{pull} de $c$}}\\
      }
      \ElseIf{possuo o conteúdo $c$ e não sou o servidor origem de $c$ e $bi^{c} > bm^{c}$}{
        \emph{\textbf{Insiro na minha lista de operações a \emph{remoção} de $c$}}\\
      }
    }

    \While{$load_{i} > HW$}{
        Fazer \emph{push} da réplica do conteúdo $c$ para $j \in S$ tal que $\max(d^{ic}_{j})$\\
        \emph{\textbf{Insiro na minha lista de operações o \emph{push} de $c$ para $j$}}
        $load_{i} \leftarrow load_{i} - d^{ic}_{j}$\\
    }

    \caption{Algoritmo Heurístico Online, populando a \emph{lista de operações}}
    \label{aholo}
\end{algorithm}

Uma vez que os servidores tenham preenchido suas \emph{LO}, eles podem começar a enviar as operações que efetuarão para os demais servidores. Isso é feito através de propagação por inundação ou \emph{broadcast} usando a função \emph{MPI\_Bcast()}.

Como as \emph{LO} de servidores diferentes podem ter tamanhos diferentes o servidor deve enviar a quantidade de operações antes de enviar as próprias operações. Assim, quem está recebendo sabe quantas mensagens deve esperar.

\begin{figure}[h]
    \centering
    \includegraphics[scale=0.5]{images/broadcast_data.png}

    \caption{Servidor enviando as operações para os demais servidores da \emph{MCDN}}
\end{figure}

Os servidores não podem enviar as suas operações ao mesmo tempo, então enquanto um servidor $S$ está enviando, os outros estarão escutando as mensagens \emph{broadcast} de $S$. Isso é feito usando a função \emph{MPI\_Bcast()} coordenada com \emph{MPI\_Rank}.

\begin{algorithm}[H]

    \small
    \SetLine

    \For{$sender \leftarrow 0$ \KwTo $nSERVERS$}{
        MPI\_Bcast($\cdots, number\_of\_operations, sender, \cdots$)\\
        \For{$counter \leftarrow 0$ \KwTo $number\_of\_operations$}{
            MPI\_Bcast($\cdots, operation, sender, \cdots$)\\
            Atualiza o \emph{VLS} de acordo com \emph{operation}
        }
    }

    \caption{\emph{Broadcast} da \emph{lista de operações} por todos os servidores}
    \label{broadcast}
\end{algorithm}

\begin{figure}[h]
    \centering
    \includegraphics[scale=0.5]{images/broadcast_turn.png}

    \caption{Servidor enviando as operações para os demais servidores da \emph{MCDN}}
\end{figure}

Essa medida garante que todos os servidores enviarão suas operações e que serão escutados. Como todos terão ciência de todas as operações efetuadas, basta que atualizem suas \emph{VLS} de acordo com as operações, isso garante a consistência da \emph{VLS} entre os servidores.
